from  typing import List
# 在 x 轴上有一个一维的花园。花园长度为 n，从点 0 开始，到点 n 结束。
#
# 花园里总共有 n + 1 个水龙头，分别位于 [0, 1, ..., n] 。
#
# 给你一个整数 n 和一个长度为 n + 1 的整数数组 ranges ，其中 ranges[i] （下标从 0 开始）表示：如果打开点 i 处的水龙头，可以灌溉的区域为 [i -  ranges[i], i + ranges[i]] 。
#
# 请你返回可以灌溉整个花园的 最少水龙头数目 。如果花园始终存在无法灌溉到的地方，请你返回 -1 。
#
# 来源：力扣（LeetCode）
# 链接：https://leetcode-cn.com/problems/minimum-number-of-taps-to-open-to-water-a-garden
# 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
class Solution:
    def minTaps(self, n: int, ranges: List[int]) -> int:
        dp = [-1 for i in range(n+1)]
        dp[0] = 0

        for idx in range(0,n+1):
            ran = ranges[idx]
            l = max(0,idx-ran)
            r = min(n,idx+ran)

            if dp[l] == -1:
                continue
            else:
                for pos in range(l,r+1):
                    print(pos)
                    if dp[pos]>=0:
                        dp[pos] = min(dp[pos],dp[l]+1)
                    else:
                        dp[pos] = dp[l]+1

        print(dp)
        return dp[n]

res = Solution().minTaps(n = 5, ranges = [3,4,1,1,0,0])
print(res)



